package Solutions

import "strconv"

func isAdditiveNumber(num string) bool {
	l := len(num)
	stack := make([]int, l)
	st := -1
	for i := 1; i < l; i++ {
		if i > l/2 || num[0] == '0' && i != 1 {
			break
		}
		st++
		stack[st], _ = strconv.Atoi(num[0:i])
		for j := i + 1; j < l; j++ {
			if l-j < j-i {
				break
			}
			if num[i] == '0' && j != i+1 {
				break
			}
			st++
			stack[st], _ = strconv.Atoi(num[i:j])
			ans := isADfs(stack, st, num, j)
			if ans {
				return ans
			}
			st--
		}
		st--
	}
	return false
}

func isADfs(stack []int, st int, num string, j int) bool {
	if j == len(num) {
		return true
	}
	target := stack[st] + stack[st-1]
	if num[j] == '0' && target != 0 {
		return false
	}
	for k := j + 1; k <= len(num); k++ {
		n, _ := strconv.Atoi(num[j:k])
		if target == n {
			st++
			stack[st] = target
			return isADfs(stack, st, num, k)
		} else if target < n {
			return false
		}
	}
	return false
}
